{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #数组中的第 K 个最大元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #divide-and-conquer #quickselect #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #分治 #快速选择 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findKthLargest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组中的第 K 个最大元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定整数数组 <code>nums</code> 和整数 <code>k</code>，请返回数组中第 <code><strong>k</strong></code> 个最大的元素。</p>\n",
    "\n",
    "<p>请注意，你需要找的是数组排序后的第 <code>k</code> 个最大的元素，而不是第 <code>k</code> 个不同的元素。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> <code>[3,2,1,5,6,4] 和</code> k = 2\n",
    "<strong>输出:</strong> 5\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> <code>[3,2,3,1,2,4,5,5,6] 和</code> k = 4\n",
    "<strong>输出:</strong> 4</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示： </strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup>&nbsp;&lt;= nums[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 215&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/kth-largest-element-in-an-array/\">https://leetcode-cn.com/problems/kth-largest-element-in-an-array/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [xx4gT2](https://leetcode.cn/problems/xx4gT2/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [xx4gT2](https://leetcode.cn/problems/xx4gT2/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        s = []\n",
    "\n",
    "        for n in nums:\n",
    "            if len(s) < k:\n",
    "                heapq.heappush(s, n)\n",
    "            else:\n",
    "                if n > s[0]:\n",
    "                    heapq.heappop(s)\n",
    "                    heapq.heappush(s, n)\n",
    "        return s[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "         return (sorted(nums)[-k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        while len(nums) > k:\n",
    "            heapq.heappop(nums)\n",
    "        return nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://mp.weixin.qq.com/s/8ZTMhvHJK_He48PpSt_AmQ\n",
    "\n",
    "import random\n",
    "class Solution:\n",
    "    # 快速选择算法:快排变种 ，但是会超时\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        nums = self.suffle(nums)\n",
    "        l = 0\n",
    "        r = len(nums) - 1\n",
    "        k_ = len(nums) - k\n",
    "        while l <= r:\n",
    "            pos = self.partition(nums, l, r)\n",
    "            if pos < k_:\n",
    "                lo = pos + 1\n",
    "            elif pos > k_:\n",
    "                r = pos - 1\n",
    "            else:\n",
    "                return nums[pos]\n",
    "        \n",
    "        return -1\n",
    "\n",
    "    def partition(self, nums, l, r):\n",
    "        point = random.randint(l, r)\n",
    "        nums[point], nums[r] = nums[r], nums[point]\n",
    "\n",
    "        pivot = nums[r]\n",
    "        i = l - 1\n",
    "        for j in range(l, r):\n",
    "            if nums[j] <= pivot:\n",
    "                i += 1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "        \n",
    "        nums[i+1], nums[r] = nums[r], nums[i+1]\n",
    "\n",
    "        return i+1\n",
    "\n",
    "    def suffle(self, nums):\n",
    "        for i in range(len(nums) - 1, 0, -1):\n",
    "            j = random.randint(0, i)\n",
    "            nums[i], nums[j] = nums[j], nums[i]\n",
    "        \n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        arr = sorted(nums)\n",
    "        return arr[len(nums)-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-k]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        nums = [-1*i for i in nums]\n",
    "        heapq.heapify(nums)\n",
    "        for _ in range(k-1):\n",
    "            heapq.heappop(nums)\n",
    "        return -1 * heapq.heappop(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def quickFind(self, nums, start, end, k):\n",
    "        if start == end:\n",
    "            return nums[start]\n",
    "        left, right = start, end\n",
    "        pivot = nums[left + (right - left) // 2]\n",
    "        while left <= right:\n",
    "            while left <= right and nums[left] > pivot:\n",
    "                left += 1\n",
    "            while left <= right and nums[right] < pivot:\n",
    "                right -= 1\n",
    "            if left <= right:\n",
    "                nums[left], nums[right] = nums[right], nums[left]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        if start + k - 1 <= right:\n",
    "            return self.quickFind(nums, start, right, k)\n",
    "        if start + k - 1 >= left:\n",
    "            return self.quickFind(nums, left, end, k - (left - start))\n",
    "        return nums[right + 1]\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        return self.quickFind(nums, 0 ,len(nums)-1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def quick_sort(nums):\n",
    "            if len(nums) <= 1:\n",
    "                return nums\n",
    "            \n",
    "            mid = len(nums)//2\n",
    "            left = [x for x in nums if x < nums[mid]]\n",
    "            m = [x for x in nums if x == nums[mid]]\n",
    "            right = [x for x in nums if x > nums[mid]]   \n",
    "            \n",
    "            return quick_sort(left)+m+quick_sort(right)\n",
    "\n",
    "        nums_sort = quick_sort(nums)\n",
    "        return nums_sort[-k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def quick_sort(nums):\n",
    "            if len(nums) <= 1:\n",
    "                return nums\n",
    "            \n",
    "            mid = len(nums)//2\n",
    "            left = [x for x in nums if x < nums[mid]]\n",
    "            m = [x for x in nums if x == nums[mid]]\n",
    "            right = [x for x in nums if x > nums[mid]]   \n",
    "            \n",
    "            return quick_sort(left)+m+quick_sort(right)\n",
    "\n",
    "        nums_sort = quick_sort(nums)\n",
    "        return nums_sort[-k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        sort_nums = self.quick_sort(nums)\n",
    "        # nums.sort()\n",
    "        print(sort_nums[::-1])\n",
    "        return sort_nums[::-1][k-1]\n",
    "        \n",
    "    def quick_sort(self,arr):\n",
    "        if len(arr)==0:return arr\n",
    "        if len(arr)==1:return arr\n",
    "        base = arr[len(arr)//2]\n",
    "        arr.remove(base)\n",
    "        left = [val for val in arr if val < base]\n",
    "        right = [val for val in arr if val >= base]\n",
    "        sort_left = self.quick_sort(left)\n",
    "        sort_right = self.quick_sort(right)\n",
    "        return sort_left + [base] + sort_right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        def binary_split(start,end):\n",
    "            randi = random.randint(start, end-1)\n",
    "            nums[start], nums[randi] = nums[randi], nums[start]\n",
    "            key = nums[start]\n",
    "            l,r = start, end \n",
    "            i = l+1\n",
    "            while i<r:\n",
    "                if nums[i] > key:\n",
    "                    nums[l], nums[i] = nums[i], nums[l]\n",
    "                    l += 1\n",
    "                    i += 1\n",
    "                elif nums[i] == key:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    r -= 1\n",
    "                    nums[i], nums[r] = nums[r], nums[i]\n",
    "            if l >= k:\n",
    "                return binary_split(start, l)\n",
    "            elif r>=k:\n",
    "                return nums[k-1]\n",
    "            else:\n",
    "                return binary_split(r, end)\n",
    "\n",
    "        return binary_split(0, len(nums))\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def sort(i,n):\n",
    "            left=2*i+1  \n",
    "            right=2*i+2 \n",
    "\n",
    "            max_index=i \n",
    "            if left<n and nums[left]>nums[max_index]: \n",
    "                max_index=left \n",
    "            if right<n and nums[max_index]<nums[right]:\n",
    "                max_index=right\n",
    "\n",
    "            if max_index!=i: \n",
    "                nums[max_index],nums[i]=nums[i],nums[max_index]\n",
    "                sort(max_index,n) \n",
    "\n",
    "        n=len(nums) \n",
    "        for i in range(n//2,-1,-1):\n",
    "            sort(i,n)\n",
    "\n",
    "        for i in range(n-1,n-k-1,-1):\n",
    "            nums[0],nums[i]=nums[i],nums[0]\n",
    "            sort(0,i)  \n",
    "\n",
    "        return nums[n-k]  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "import random\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        def quick_sort(begin, end):\n",
    "            if begin >= end:\n",
    "                return\n",
    "            pviot = random.randint(begin, end)\n",
    "            left = begin\n",
    "            right = end\n",
    "            target = nums[pviot]\n",
    "            nums[left], nums[pviot] = nums[pviot], nums[left]\n",
    "            while left < right:\n",
    "                while left < right and nums[right] >= target:\n",
    "                    right -= 1\n",
    "                nums[left] = nums[right]\n",
    "                while left < right and nums[left] <= target:\n",
    "                    left += 1\n",
    "                nums[right] = nums[left]\n",
    "            nums[left] = target\n",
    "            if left == n - k:\n",
    "                return\n",
    "            elif left > n - k:\n",
    "                quick_sort(begin, left - 1)\n",
    "            else:\n",
    "                quick_sort(left + 1, end)\n",
    "        quick_sort(0, n - 1)\n",
    "        print(nums)\n",
    "        return nums[-k]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "import random\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        def quick_sort(begin, end):\n",
    "            if begin >= end:\n",
    "                return\n",
    "            pviot = random.randint(begin, end)\n",
    "            left = begin\n",
    "            right = end\n",
    "            target = nums[pviot]\n",
    "            nums[left], nums[pviot] = nums[pviot], nums[left]\n",
    "            while left < right:\n",
    "                while left < right and nums[right] >= target:\n",
    "                    right -= 1\n",
    "                nums[left] = nums[right]\n",
    "                while left < right and nums[left] <= target:\n",
    "                    left += 1\n",
    "                nums[right] = nums[left]\n",
    "            nums[left] = target\n",
    "            quick_sort(begin, left - 1)\n",
    "            quick_sort(left + 1, end)\n",
    "        quick_sort(0, n - 1)\n",
    "        print(nums)\n",
    "        return nums[-k]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        sort_nums = self.quick_sort(nums)\n",
    "        # nums.sort()\n",
    "        print(sort_nums[::-1])\n",
    "        return sort_nums[::-1][k-1]\n",
    "        \n",
    "    def quick_sort(self,arr):\n",
    "        if len(arr)==0:\n",
    "            return arr\n",
    "        if len(arr)==1:\n",
    "            return arr\n",
    "        base = arr[len(arr)//2]\n",
    "        arr.remove(base)\n",
    "        print(arr)\n",
    "        print(\"base:\",base)\n",
    "        left = [val for val in arr if val < base]\n",
    "        right = [val for val in arr if val >= base]\n",
    "        sort_left = self.quick_sort(left)\n",
    "        sort_right = self.quick_sort(right)\n",
    "        return sort_left+[base]+sort_right\n",
    "    def quick_sort1(self,data):    \n",
    "        \"\"\"快速排序\"\"\"    \n",
    "        if len(data) >= 2:  # 递归入口及出口        \n",
    "            mid = data[len(data)//2]  # 选取基准值，也可以选取第一个或最后一个元素        \n",
    "            left, right = [], []  # 定义基准值左右两侧的列表        \n",
    "            data.remove(mid)  # 从原始数组中移除基准值        \n",
    "            for num in data:            \n",
    "                if num >= mid:                \n",
    "                    right.append(num)            \n",
    "                else:                \n",
    "                    left.append(num)        \n",
    "            return self.quick_sort1(left) + [mid] + self.quick_sort1(right)    \n",
    "        else:        \n",
    "            return data\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        k = len(nums) - k\n",
    "        def quick_sort(left, right):\n",
    "\n",
    "            if left == right:\n",
    "                return nums[left]\n",
    "\n",
    "            pivot = random.randint(left, right)\n",
    "            pivot_value = nums[pivot]\n",
    "\n",
    "            nums[left], nums[pivot] = nums[pivot], nums[left]\n",
    "\n",
    "            while left<right:\n",
    "\n",
    "                while left<right:\n",
    "\n",
    "                    if nums[right]<pivot_value:\n",
    "                        nums[left] = nums[right]\n",
    "                        left+=1\n",
    "                        break\n",
    "\n",
    "                    else:\n",
    "                        right -= 1\n",
    "\n",
    "                    \n",
    "                while left<right:\n",
    "                    if nums[left]>=pivot_value:\n",
    "                        nums[right] = nums[left]\n",
    "                        right -= 1\n",
    "                        break\n",
    "                    else:\n",
    "                        left += 1\n",
    "\n",
    "            nums[left] = pivot_value\n",
    "\n",
    "            if left==k:\n",
    "                return nums[left]\n",
    "            elif left<k:\n",
    "                return quick_sort(left+1, len(nums)-1)\n",
    "            else:\n",
    "                return quick_sort(0, left-1)\n",
    "\n",
    "\n",
    "        return quick_sort(0, len(nums)-1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def partition(arr, left, right):\n",
    "            x = arr[left]\n",
    "            while left < right:\n",
    "                if arr[right] >= x:\n",
    "                    right -= 1\n",
    "                arr[left] = arr[right]\n",
    "                if arr[left] < x:\n",
    "                    left += 1\n",
    "                arr[right] = arr[left]\n",
    "            nums[left] = x\n",
    "            return left\n",
    "        \n",
    "        def quickSelect(arr, left, right, index):\n",
    "            q = partition(arr, left, right)\n",
    "            if q == index:\n",
    "                return arr[q]\n",
    "            if q < index:\n",
    "                return quickSelect(arr, q + 1, right, index)\n",
    "            else:\n",
    "                return quickSelect(arr, left, q - 1, index)\n",
    "\n",
    "        \n",
    "        n = len(nums)\n",
    "        left, right = 0, n - 1\n",
    "        rand = random.randint(0, len(nums) - 1)\n",
    "        nums[left], nums[rand] = nums[rand], nums[left]\n",
    "        return quickSelect(nums, left, right, n - k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 1: return nums[0]\n",
    "        return self.kth(nums, 0, len(nums)-1, k-1)\n",
    "    \n",
    "\n",
    "    def kth(self, nums, beg, end, idx):\n",
    "        p = beg\n",
    "        l, r = beg, end\n",
    "        while l < r:\n",
    "            while l < r and nums[r] < nums[p]:\n",
    "                r -= 1\n",
    "            while l < r and nums[l] >= nums[p]:\n",
    "                l += 1\n",
    "            nums[l], nums[r] = nums[r], nums[l]\n",
    "        # print(nums, l)\n",
    "        nums[l], nums[p] = nums[p], nums[l]\n",
    "        # print(nums, l)\n",
    "        if l == idx:\n",
    "            return nums[r]\n",
    "        elif l < idx:\n",
    "            return self.kth(nums, l+1, end, idx)\n",
    "        else:\n",
    "            return self.kth(nums, beg, l-1, idx)\n",
    "\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        return self.qs(nums, 0, len(nums) - 1, k)\n",
    "    \n",
    "    def qs(self, nums, l, r, k):\n",
    "        i, j = l, r\n",
    "        pivot = nums[l]\n",
    "        while l < r:\n",
    "            while l < r and nums[r] <= pivot:\n",
    "                r -= 1\n",
    "            nums[l] = nums[r]\n",
    "            while l < r and nums[l] >= pivot:\n",
    "                l += 1\n",
    "            nums[r] = nums[l]\n",
    "        nums[r] = pivot\n",
    "        if l == k - 1:\n",
    "            return nums[l]\n",
    "        elif l < k - 1:\n",
    "            return self.qs(nums, l + 1, j, k)\n",
    "        else:\n",
    "            return self.qs(nums, i, l - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        self.quickSort(nums,0,len(nums)-1,k-1)\n",
    "        return nums[k-1]\n",
    "\n",
    "    def quickSort(self,nums,left,right,k):\n",
    "        if left>=right:\n",
    "            return \n",
    "        temp=nums[left]\n",
    "        start=left\n",
    "        end=right\n",
    "        while(start<end):\n",
    "            while(start<end and nums[end]<temp):\n",
    "                end -=1\n",
    "            nums[start]=nums[end]\n",
    "            while(start<end and nums[start]>=temp):\n",
    "                start+=1\n",
    "            nums[end]=nums[start]\n",
    "        nums[start]=temp\n",
    "        if k<=start:\n",
    "            self.quickSort(nums,left,start-1,k)\n",
    "        else:\n",
    "            self.quickSort(nums,start+1,right,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        self.quickSort(nums, 0, len(nums)-1)\n",
    "        return nums[len(nums)-k]\n",
    "    def quickSort(self, nums: List[int], i: int, j: int)-> None:\n",
    "        if i > j:\n",
    "            return nums\n",
    "        pivot = nums[i]\n",
    "        low = i\n",
    "        high = j\n",
    "        while i < j:\n",
    "            while i < j and nums[j] >= pivot:\n",
    "                j -= 1\n",
    "            nums[i] = nums[j]\n",
    "            while i < j and nums[i] < pivot:\n",
    "                i += 1\n",
    "            nums[j] = nums[i]\n",
    "        nums[i] = pivot\n",
    "        self.quickSort(nums, low, i-1)\n",
    "        self.quickSort(nums, i+1, high)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partion(self, arr, l, r):\n",
    "        # ind = random.randint(l, r)\n",
    "        # arr[l], arr[ind] = arr[ind], arr[l]\n",
    "        stand = arr[l]\n",
    "        i, j = l + 1, r\n",
    "        while True:\n",
    "            while i <= r and arr[i] < stand:\n",
    "                i += 1\n",
    "            while j >= l + 1 and arr[j] > stand:\n",
    "                j -= 1\n",
    "            if i > j:\n",
    "                break\n",
    "            else:\n",
    "                arr[i], arr[j] = arr[j], arr[i]\n",
    "                i += 1\n",
    "                j -= 1\n",
    "        arr[j], arr[l] = arr[l], arr[j]\n",
    "        return j\n",
    "\n",
    "    def threeQuickSort(self, arr, left, right, target):\n",
    "        if left <= right:\n",
    "            mid = self.partion(arr, left, right)\n",
    "            if target == mid:\n",
    "                print(mid)\n",
    "                return arr[mid]\n",
    "            elif target < mid:\n",
    "                return self.threeQuickSort(arr, left, mid - 1, target)\n",
    "            else:\n",
    "                return self.threeQuickSort(arr, mid + 1, right, target)\n",
    "\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        res = self.threeQuickSort(nums, 0, len(nums) - 1, len(nums) - k)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, nums, start, end):\n",
    "        i = start\n",
    "        for j in range(start, end):\n",
    "            if nums[j] > nums[end]:\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "                i += 1\n",
    "        nums[i], nums[end] = nums[end], nums[i]\n",
    "        return i\n",
    "\n",
    "    def quick_sort(self, nums, start, end, k):\n",
    "        p = self.partition(nums, start, end)\n",
    "        if p - start + 1 < k:\n",
    "            self.quick_sort(nums, p + 1, end, k - p + start - 1)\n",
    "        elif p - start + 1 > k:\n",
    "            self.quick_sort(nums, start, p - 1, k)\n",
    "        else:\n",
    "            return\n",
    "\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        self.quick_sort(nums, 0, len(nums) - 1, k)\n",
    "        return nums[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, nums: List[int], left: int, right: int):\n",
    "        while left < right:\n",
    "            while left < right and nums[left] <= nums[right]:\n",
    "                right -= 1\n",
    "            nums[left], nums[right] = nums[right], nums[left]\n",
    "            while left < right and nums[left] <= nums[right]:\n",
    "                left += 1\n",
    "            nums[left], nums[right] = nums[right], nums[left]\n",
    "        return left\n",
    "\n",
    "    def quickSort(self, nums: List[int], left: int, right: int):\n",
    "        if left < right:\n",
    "            pivot = self.partition(nums, left, right)\n",
    "            self.quickSort(nums, left, pivot - 1)\n",
    "            self.quickSort(nums, pivot + 1, right)\n",
    "\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        self.quickSort(nums, 0, n - 1)\n",
    "        return nums[n - k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        return self.partition(nums, 0, len(nums) - 1, k)\n",
    "\n",
    "    def partition(self, nums, l, r, k):\n",
    "        if l > r: return -1\n",
    "\n",
    "        base = nums[l]\n",
    "        w = r + 1\n",
    "        for i in range(r, l-1, -1):\n",
    "            if nums[i] >= base:\n",
    "                w -= 1\n",
    "                nums[w], nums[i] = nums[i], nums[w]\n",
    "\n",
    "        if len(nums) - w == k:\n",
    "            return nums[w]\n",
    "        elif len(nums) - w > k:\n",
    "            res = self.partition(nums, w+1, r, k)\n",
    "        else:\n",
    "            res = self.partition(nums, l, w-1, k)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        return quicksort(nums, 0, len(nums) - 1, k)\n",
    "\n",
    "def quicksort(nums: List[int], start_i, end_i, k):\n",
    "    if start_i >= end_i:\n",
    "        return nums[start_i]\n",
    "    i = start_i - 1\n",
    "    sample = nums[end_i]\n",
    "    for j in range(start_i, end_i):\n",
    "        if nums[j] > sample:\n",
    "            i += 1\n",
    "            tmp = nums[j]\n",
    "            nums[j] = nums[i]\n",
    "            nums[i] = tmp\n",
    "    i += 1\n",
    "    if i == k - 1:\n",
    "        return sample\n",
    "    nums[end_i] = nums[i]\n",
    "    nums[i] = sample\n",
    "    if i < k - 1:\n",
    "        return quicksort(nums, i + 1, end_i, k)\n",
    "    else:\n",
    "        return quicksort(nums, start_i, i - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        return fastsort(nums, 0, len(nums) - 1, k )\n",
    "\n",
    "def fastsort(nums, start, end, k):\n",
    "    if start == end and k == 1: return nums[start]\n",
    "    i = start\n",
    "    j = end\n",
    "    base = start\n",
    "    while i < j:\n",
    "        while i < j and nums[j] >= nums[base]: j -= 1\n",
    "        while i < j and nums[i] <= nums[base]: i += 1\n",
    "        temp = nums[i];nums[i] = nums[j];nums[j] = temp\n",
    "    temp = nums[i];nums[i] = nums[base];nums[base] = temp\n",
    "    base = i   \n",
    "    if end - base + 1 == k: return nums[base]\n",
    "    elif end - base + 1 > k: return fastsort(nums, base + 1, end, k)\n",
    "    else: return fastsort(nums, start, base - 1, k - (end - base + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        size = len(nums)\n",
    "        self.qsort(nums, 0, len(nums) - 1, size - k)\n",
    "        return nums[size-k]\n",
    "\n",
    "    def qsort(self, arr, left, right, k):\n",
    "        if left >= right:\n",
    "            return\n",
    "\n",
    "        v = arr[right]\n",
    "        index = left \n",
    "        for i in range(left, right):\n",
    "            if arr[i] <= v:\n",
    "                tmp = arr[i]\n",
    "                arr[i] = arr[index]\n",
    "                arr[index] = tmp\n",
    "                index += 1\n",
    "\n",
    "        tmp = arr[index]\n",
    "        arr[index] = arr[right]\n",
    "        arr[right] = tmp\n",
    "\n",
    "        if index == k:\n",
    "            return\n",
    "        elif index < k:\n",
    "            self.qsort(arr, index + 1, right, k)\n",
    "        else:\n",
    "            self.qsort(arr, left, index - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "\n",
    "        def quick_sort(left, right):\n",
    "\n",
    "            pivot = random.randint(left, right)\n",
    "            nums[left], nums[pivot] = nums[pivot], nums[left]\n",
    "\n",
    "            # pivot = left\n",
    "            pivot_value = nums[left]\n",
    "\n",
    "            while left<right:\n",
    "\n",
    "                while left<right:\n",
    "                    if nums[right]<pivot_value:\n",
    "                        nums[left] = nums[right]\n",
    "                        left += 1\n",
    "                        break\n",
    "\n",
    "                    else:\n",
    "                        right -= 1\n",
    "\n",
    "                while left<right:\n",
    "                    if nums[left]>=pivot_value:\n",
    "                        nums[right] = nums[left]\n",
    "                        right -= 1\n",
    "                        break\n",
    "\n",
    "                    else:\n",
    "                        left += 1\n",
    "\n",
    "            nums[left] = pivot_value\n",
    "\n",
    "            if left==len(nums)-k:\n",
    "                return nums[left]\n",
    "            \n",
    "            elif left<len(nums)-k:\n",
    "                return quick_sort(left+1, len(nums)-1)\n",
    "            else:\n",
    "                return quick_sort(0, left-1)\n",
    "\n",
    "        \n",
    "\n",
    "        return quick_sort(0, len(nums)-1)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def partition(self, nums, l, r):\n",
    "        privot = nums[l]\n",
    "        while l < r:\n",
    "            while l<r and nums[r] >= privot:\n",
    "                r-=1\n",
    "            nums[l] = nums[r]\n",
    "\n",
    "            while l<r and nums[l] <= privot:\n",
    "                l+=1\n",
    "            nums[r] = nums[l]\n",
    "        nums[l] = privot\n",
    "        return l\n",
    "    def quickSort(self, nums, l, r, k):\n",
    "        \n",
    "        p = self.partition(nums, l, r)\n",
    "\n",
    "        if p == len(nums)-k:\n",
    "            return nums[p]\n",
    "        elif p > len(nums)-k:\n",
    "            return self.quickSort(nums, l, p, k)\n",
    "        else:\n",
    "            return self.quickSort(nums, p+1, r, k)\n",
    "\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        #使用快排思想\n",
    "        return self.quickSort(nums, 0, len(nums)-1, k)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def partition(nums,left,right):\n",
    "            if left>=right:\n",
    "                return \n",
    "            l = left\n",
    "            r = right\n",
    "            ptr = nums[l]\n",
    "            while l<r:\n",
    "                while l<r and nums[r]>ptr:\n",
    "                    r -=1\n",
    "                nums[l] = nums[r]\n",
    "                while l<r and nums[l]<=ptr:\n",
    "                    l+=1\n",
    "                nums[r] = nums[l]\n",
    "            nums[l] = ptr\n",
    "            return l\n",
    "        def top_k(nums,k,left,right):\n",
    "            if left<right:\n",
    "                index = partition(nums,left,right)\n",
    "                if index == k:\n",
    "                    return \n",
    "                elif index<k:\n",
    "                    top_k(nums,k,index+1,right)\n",
    "                else:\n",
    "                    top_k(nums,k,left,index-1)\n",
    "        top_k(nums,len(nums)-k,0,len(nums)-1)\n",
    "        return nums[len(nums)-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        self.ans = -1\n",
    "        self.k = k\n",
    "        self.nums = nums[:]\n",
    "        self.quickSort(0, len(nums)-1)\n",
    "        return self.ans\n",
    "    \n",
    "    def quickSort(self, low, high):\n",
    "        if low > high:\n",
    "            return \n",
    "        #len=10, p=5, k=2, ans_p=8, \n",
    "        p = self.partrition(low, high)\n",
    "        # print(self.nums,p)\n",
    "        if len(self.nums) - p == self.k:\n",
    "            self.ans = self.nums[p]\n",
    "            return \n",
    "        \n",
    "        elif len(self.nums) - p > self.k:\n",
    "            self.quickSort(p+1, high)\n",
    "        else:\n",
    "            self.quickSort(low, p-1)\n",
    "\n",
    "    def partrition(self, low, high):\n",
    "        while low < high:\n",
    "            while high > low and self.nums[high] > self.nums[low]:\n",
    "                high -= 1\n",
    "            if high == low:\n",
    "                break\n",
    "            self.nums[high], self.nums[low] = self.nums[low], self.nums[high]\n",
    "            low += 1\n",
    "            while high > low and self.nums[high] > self.nums[low]:\n",
    "                low += 1\n",
    "            if high == low:\n",
    "                break\n",
    "            self.nums[high], self.nums[low] = self.nums[low], self.nums[high]\n",
    "            high -= 1\n",
    "        # print(low, high)\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        self.k = k - 1\n",
    "        self.quick_sort(nums, 0, len(nums))\n",
    "        return nums[k-1]\n",
    "    \n",
    "    def quick_sort(self, nums, left, right):\n",
    "        if right - left <= 1:\n",
    "            return\n",
    "        pivot = self.partition(nums, left, right)\n",
    "        if pivot == self.k:\n",
    "            return\n",
    "        elif pivot > self.k:\n",
    "            self.quick_sort(nums, left, pivot)\n",
    "        else:\n",
    "            self.quick_sort(nums, pivot+1, right)\n",
    "    \n",
    "    def partition(self, nums, left, right):\n",
    "        pivot = nums[left]\n",
    "        st_idx = left\n",
    "        for idx in range(left + 1, right):\n",
    "            if nums[idx] > pivot:\n",
    "                st_idx += 1\n",
    "                tmp = nums[idx]\n",
    "                nums[idx] = nums[st_idx]\n",
    "                nums[st_idx] = tmp\n",
    "        \n",
    "        nums[left] = nums[st_idx]\n",
    "        nums[st_idx] = pivot\n",
    "        return st_idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        self.quick_sort(nums, 0, len(nums))\n",
    "        return nums[-k]\n",
    "    \n",
    "    def quick_sort(self, nums, left, right):\n",
    "        if right - left <= 1:\n",
    "            return\n",
    "        pivot = self.partition(nums, left, right)\n",
    "        self.quick_sort(nums, left, pivot)\n",
    "        self.quick_sort(nums, pivot+1, right)\n",
    "    \n",
    "    def partition(self, nums, left, right):\n",
    "        pivot = nums[left]\n",
    "        st_idx = left\n",
    "        for idx in range(left + 1, right):\n",
    "            if nums[idx] < pivot:\n",
    "                st_idx += 1\n",
    "                tmp = nums[idx]\n",
    "                nums[idx] = nums[st_idx]\n",
    "                nums[st_idx] = tmp\n",
    "        \n",
    "        nums[left] = nums[st_idx]\n",
    "        nums[st_idx] = pivot\n",
    "        return st_idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def partition(lis,left, right):\n",
    "            temp = lis[left]\n",
    "            left = left\n",
    "            right = right\n",
    "            while left < right:\n",
    "                while lis[right] <= temp and left < right:\n",
    "                    right -= 1\n",
    "                lis[left] = lis[right]\n",
    "                while lis[left] >= temp and left < right:\n",
    "                    left += 1\n",
    "                lis[right] = lis[left]\n",
    "            lis[left] = temp\n",
    "            return left\n",
    "        def quick_sort(lis, left, right):\n",
    "            if left < right:\n",
    "                mid = partition(lis, left, right)\n",
    "                quick_sort(lis, left, mid-1)\n",
    "                quick_sort(lis, mid+1, right)\n",
    "        \n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        right = n-1\n",
    "        quick_sort(nums, left, right)\n",
    "        return nums[k-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "             \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        # nums.sort(reverse=True)\n",
    "        # return nums[k-1]\n",
    "        # 快速排序\n",
    "        def quick_sort(array, l, r):\n",
    "            if l < r:\n",
    "                q = partition(array, l, r)\n",
    "                if q == k - 1:\n",
    "                    return\n",
    "                quick_sort(array, l, q - 1)\n",
    "                quick_sort(array, q + 1, r)\n",
    "\n",
    "        def partition(array, l, r):\n",
    "            x = array[r]\n",
    "            i = l - 1\n",
    "            for j in range(l, r):\n",
    "                if array[j] >= x:\n",
    "                    i += 1\n",
    "                    array[i], array[j] = array[j], array[i]\n",
    "            array[i + 1], array[r] = array[r], array[i+1]\n",
    "            return i + 1\n",
    "        \n",
    "        quick_sort(nums, 0, len(nums)-1)\n",
    "        return nums[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def fastsort(start,end):\n",
    "            if start>=end:return\n",
    "            left,right,mid=start,end,nums[start]\n",
    "            while left<right:\n",
    "                while nums[right]>=mid and left<right:\n",
    "                    right-=1\n",
    "                nums[left]=nums[right]\n",
    "                while nums[left]<=mid and left<right:\n",
    "                    left+=1\n",
    "                nums[right]=nums[left]\n",
    "            nums[left]=mid\n",
    "            if left==self.length-k:return\n",
    "            fastsort(start, left-1)\n",
    "            fastsort(left+1, end)\n",
    "\n",
    "        self.length=len(nums)\n",
    "        fastsort(0, self.length-1)\n",
    "        return nums[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def swap(a, b):\n",
    "            return b, a\n",
    "\n",
    "        def quickSort(nums: List[int], l: int, r: int):\n",
    "            if l > r:\n",
    "                return\n",
    "            flag = nums[l]\n",
    "            # [l, low]元素都小于等于flag\n",
    "            low = l\n",
    "            # (low, i-1]元素都大于flag\n",
    "            for i in range(l+1, r+1):\n",
    "                if nums[i] <= flag:\n",
    "                    low = low + 1\n",
    "                    nums[low], nums[i] = swap(nums[low], nums[i])\n",
    "            nums[l], nums[low] = swap(nums[l], nums[low])\n",
    "            if low + k == len(nums):\n",
    "                return flag\n",
    "            elif low + k > len(nums):\n",
    "                return quickSort(nums, l, low-1)\n",
    "            else:\n",
    "                return quickSort(nums, low+1, r)\n",
    "\n",
    "        kLargest = quickSort(nums, 0, len(nums)-1)\n",
    "        return kLargest\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def quicksort(l, r, k):\n",
    "            if l >= r:\n",
    "                return nums[r]\n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while i < j and nums[j] <= nums[l]: j -= 1\n",
    "                while i < j and nums[i] >= nums[l]: i += 1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "            nums[i], nums[l] = nums[l], nums[i]\n",
    "            # print(nums, i)\n",
    "            if i == k-1:\n",
    "                return nums[k-1]\n",
    "            elif i > k-1:\n",
    "                return quicksort(0, i-1, k)\n",
    "            else:\n",
    "                return quicksort(i+1, r, k)\n",
    "        return quicksort(0, len(nums)-1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def partition(nums, l, r):\n",
    "            x=nums[r]\n",
    "            i=l-1\n",
    "            for j in range(l, r):\n",
    "                if nums[j]>x:\n",
    "                    j+=1\n",
    "                else:\n",
    "                    i+=1\n",
    "                    nums[i], nums[j]=nums[j], nums[i]\n",
    "                    j+=1\n",
    "            nums[i+1], nums[r]=nums[r], nums[i+1]\n",
    "            return i+1\n",
    "\n",
    "        def findK(nums, l, r, k):\n",
    "            # print(nums, l, r, k)\n",
    "            if l==r:\n",
    "                return nums[l]\n",
    "            \n",
    "            idx=partition(nums, l, r)\n",
    "            if idx-l+1==k:\n",
    "                return nums[idx]\n",
    "            elif idx-l+1<k:\n",
    "                return findK(nums, idx+1, r, k-(idx-l+1))\n",
    "            else:\n",
    "                return findK(nums, l, idx-1, k)\n",
    "        \n",
    "        n=len(nums)\n",
    "        return findK(nums, 0, n-1, n+1-k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def find(nums, l, r, k):\n",
    "            if l+1==r: return nums[l]\n",
    "            p = nums[l]\n",
    "            i = l+1\n",
    "            for j in range(l+1, r):\n",
    "                if nums[j] <p:\n",
    "                    nums[j], nums[i] = nums[i], nums[j]\n",
    "                    i+=1\n",
    "\n",
    "            nums[i-1], nums[l] = nums[l], nums[i-1]\n",
    "            # print(nums, l,r,k,i,p)\n",
    "            if i-l == k:\n",
    "                return nums[i-1]\n",
    "            if i-l > k:\n",
    "                return find(nums, l, i, k)\n",
    "            return find(nums, i, r, k-i+l)\n",
    "\n",
    "\n",
    "        return find(nums, 0, len(nums), len(nums)+1-k)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        import random\n",
    "\n",
    "        def quicksort(low, high):\n",
    "            if low >= high:\n",
    "                return\n",
    "\n",
    "            # pivot_ind = random.randint(low, high)\n",
    "            # pivot = nums[pivot_ind]\n",
    "            # nums[pivot_ind], nums[low] = nums[low], nums[pivot_ind]\n",
    "            pivot = nums[low]\n",
    "            l, r = low, high\n",
    "\n",
    "            while(l<r):\n",
    "                while(l<r and nums[r] < pivot):\n",
    "                    r -= 1\n",
    "                nums[l] = nums[r]\n",
    "\n",
    "                while(l<r and nums[l] >= pivot):\n",
    "                    l += 1\n",
    "                nums[r] = nums[l]\n",
    "\n",
    "            nums[l] = pivot\n",
    "            quicksort(low, l-1)\n",
    "            quicksort(l+1, high)\n",
    "        quicksort(0, len(nums)-1)\n",
    "\n",
    "        return nums[k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        # 快排\n",
    "        \n",
    "        def partion(left, right, k):\n",
    "            # print(nums[left:right+1], k)\n",
    "            pivot = nums[right]\n",
    "            i = left \n",
    "            for j in range(left, right):\n",
    "                if nums[j] > pivot:\n",
    "                    nums[i], nums[j] = nums[j], nums[i]\n",
    "                    i += 1\n",
    "            nums[i], nums[right] = nums[right], nums[i]\n",
    "            # print(nums)\n",
    "            if i - left + 1 == k:\n",
    "                return nums[i]\n",
    "            elif i - left + 1 > k:\n",
    "                return partion(left, i-1,k)\n",
    "            elif i - left + 1 < k:\n",
    "                return partion(i+1, right, k - (i-left + 1))\n",
    "        return partion(0, len(nums)-1, k)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        # 荷兰国旗问题，将arr中小于target的至于数组左边，大于target的至于数组右边，相等则位于中间\n",
    "        def partition(arr,start,end,target):\n",
    "            if start==end:\n",
    "                return [start,end]\n",
    "            l=start\n",
    "            r=end\n",
    "            mid=l\n",
    "            while l<=r and mid<=r:\n",
    "                if arr[mid]<target:\n",
    "                    tmp=arr[mid]\n",
    "                    arr[mid]=arr[l]\n",
    "                    arr[l]=tmp\n",
    "                    l+=1\n",
    "                    mid+=1\n",
    "                elif arr[mid]>target:\n",
    "                    tmp=arr[r]\n",
    "                    arr[r]=arr[mid]\n",
    "                    arr[mid]=tmp\n",
    "                    r-=1\n",
    "                else:\n",
    "                    mid+=1\n",
    "                    # l+=1\n",
    "            # 返回目标值所在的区间范围\n",
    "            return [l,mid-1]   \n",
    "\n",
    "        def swap(arr,i,j):\n",
    "            tmp=arr[i]\n",
    "            arr[i]=arr[j]\n",
    "            arr[j]=tmp    \n",
    "\n",
    "        def get_minist_k(arr,i,j,k):\n",
    "            \n",
    "            # 先随机选择一个位置与0位置元素进行交换\n",
    "            while i<=j:\n",
    "                # idx=random.randint(0,j-i)\n",
    "                # swap(arr,i,i+idx)\n",
    "                res=partition(arr,i,j,arr[i])\n",
    "                if k>=res[0] and k<=res[1]:\n",
    "                    return arr[res[0]]\n",
    "                elif k<res[0]:\n",
    "                    return get_minist_k(arr,i,res[0]-1,k)\n",
    "                else:\n",
    "                    return get_minist_k(arr,res[1]+1,j,k)\n",
    "        return get_minist_k(nums,0,len(nums)-1,len(nums)-k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        a = nums\n",
    "        def f(start, end, k):\n",
    "            if start == end:\n",
    "                return a[start]\n",
    "            pivot = a[start]\n",
    "            i = start\n",
    "            j = end\n",
    "            while i < j:\n",
    "                while i < j and a[j] <= pivot:\n",
    "                    j -= 1\n",
    "                a[i] = a[j]\n",
    "                while i < j and a[i] >= pivot:\n",
    "                    i += 1\n",
    "                a[j] = a[i]\n",
    "            a[i] = pivot\n",
    "            l = i - start + 1\n",
    "            r = end - i\n",
    "            if l == k:\n",
    "                return pivot\n",
    "            if l > k:\n",
    "                return f(start, start + l - 1, k)\n",
    "            else:\n",
    "                return f(end - r + 1, end, k - l)\n",
    "        return f(0, len(nums) - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def quick_sort(nums, l, r, k):\n",
    "            if l == r:\n",
    "                return nums[l]\n",
    "            x = nums[l]\n",
    "            i = l - 1\n",
    "            j = r + 1\n",
    "            while i < j:\n",
    "                while True:\n",
    "                    i += 1\n",
    "                    if nums[i] <= x:\n",
    "                        break\n",
    "                while True:\n",
    "                    j -= 1\n",
    "                    if nums[j] >= x:\n",
    "                        break\n",
    "                if i < j:\n",
    "                    nums[i], nums[j] = nums[j], nums[i]\n",
    "            num_left = j - l + 1\n",
    "            if num_left >= k:\n",
    "                return quick_sort(nums, l, j, k)\n",
    "            else:\n",
    "                return quick_sort(nums, j + 1, r, k - num_left)\n",
    "        \n",
    "        return quick_sort(nums, 0, len(nums) - 1, k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        # 快速排序\n",
    "        self.nums = nums\n",
    "        self.k = k\n",
    "        return self.nums[self.quicksort(0, len(nums) - 1)]\n",
    "    \n",
    "    def quicksort(self, low, high):\n",
    "        if low < high:\n",
    "            p = self.partition(low, high)\n",
    "            if p == self.k - 1:\n",
    "                return p\n",
    "            elif p < self.k - 1:\n",
    "                return self.quicksort(p + 1, high)\n",
    "            else:\n",
    "                return self.quicksort(low, p-1)\n",
    "        return low\n",
    "\n",
    "    \n",
    "    def partition(self, low, high):\n",
    "        pivot = self.nums[low]\n",
    "        while low < high:\n",
    "            while low < high and self.nums[high] <= pivot:\n",
    "                high -= 1\n",
    "            self.nums[low] = self.nums[high]\n",
    "            while low < high and self.nums[low] >= pivot:\n",
    "                low += 1\n",
    "            self.nums[high] = self.nums[low]\n",
    "        self.nums[low] = pivot\n",
    "        return low\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        # 使用快速排序从大到小排序，如果第k-1号位置经过排序，则返回\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        def fastsort(left,right):\n",
    "            if left>right:\n",
    "                return nums[k-1]\n",
    "            i,j = left,right\n",
    "            item = nums[i]\n",
    "            flag = 0\n",
    "            while i<j:\n",
    "                if nums[j]>item and flag==0:\n",
    "                    flag = 1\n",
    "                    nums[i]=nums[j]\n",
    "                elif flag==0:\n",
    "                    j-=1\n",
    "                if nums[i]<item and flag==1:\n",
    "                    flag = 0\n",
    "                    nums[j] = nums[i]\n",
    "                elif flag==1:\n",
    "                    i+=1\n",
    "            nums[i] = item\n",
    "            if i==k-1:\n",
    "                return nums[i]\n",
    "            else:\n",
    "                if i>k-1:\n",
    "                    return fastsort(left,i-1)\n",
    "                else:\n",
    "                    return fastsort(i+1,right)\n",
    "        return fastsort(0,len(nums)-1)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def quick_sort(l, r, nums, k):\n",
    "            if l > r:\n",
    "                return\n",
    "            left, right = l, r\n",
    "            pivot = nums[left]\n",
    "            while left < right:\n",
    "                while left < right and nums[right] <= pivot:\n",
    "                    right -= 1\n",
    "                nums[left] = nums[right]\n",
    "                while left < right and nums[left] >= pivot:\n",
    "                    left += 1\n",
    "                nums[right] = nums[left]\n",
    "            nums[left] = pivot  # 将 pivot 放在最终位置\n",
    "            \n",
    "            # 现在，如果 pivot 的位置是 k-1，那么我们找到了第k大的元素\n",
    "            if left == k - 1:\n",
    "                return nums[left]\n",
    "            elif left > k - 1:\n",
    "                return quick_sort(l, left - 1, nums, k)\n",
    "            else:\n",
    "                return quick_sort(left + 1, r, nums, k)\n",
    "\n",
    "        return quick_sort(0, len(nums) - 1, nums, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def partition(nums, start, end):\n",
    "            j = start\n",
    "            for i in range(start, end):\n",
    "                if nums[i] < nums[end]:\n",
    "                    nums[i], nums[j] = nums[j], nums[i]\n",
    "                    j += 1\n",
    "            nums[j], nums[end] = nums[end], nums[j]\n",
    "            return j\n",
    "\n",
    "        def quickSelect(nums, start, end, k):\n",
    "            if start >= end:\n",
    "                return nums[start]\n",
    "            j = partition(nums, start, end)\n",
    "            if k == j:\n",
    "                return nums[k]\n",
    "            if k < j:\n",
    "                return quickSelect(nums, start, j - 1, k)\n",
    "            return quickSelect(nums, j + 1, end, k)\n",
    "        \n",
    "        return quickSelect(nums, 0, len(nums) - 1, len(nums) - k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def quick_sort(nums, l, r):\n",
    "            pivot = nums[l]\n",
    "            left = l\n",
    "            for i in range(l, r):\n",
    "                if nums[i] > pivot:\n",
    "                    left += 1\n",
    "                    nums[i], nums[left] = nums[left], nums[i]\n",
    "            nums[left], nums[l] = nums[l], nums[left]\n",
    "            if left + 1 == k:\n",
    "                return nums[left]\n",
    "            elif left + 1 > k:\n",
    "                return quick_sort(nums, l, left)\n",
    "            else:\n",
    "                return quick_sort(nums, left + 1, r)\n",
    "        return quick_sort(nums, 0, len(nums))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums) - k\n",
    "        def partition(low, high):\n",
    "            pivot = nums[low]\n",
    "            while low<high:\n",
    "                while low<high and nums[high] >= pivot:\n",
    "                    high -= 1\n",
    "                nums[low] = nums[high]\n",
    "                while low<high and nums[low] <= pivot:\n",
    "                    low += 1\n",
    "                nums[high] = nums[low]\n",
    "            nums[low] = pivot\n",
    "            return low\n",
    "        def quicksort_search(low, high):\n",
    "            \n",
    "            mid = partition(low,high)\n",
    "\n",
    "            if mid == n:\n",
    "                return nums[mid]\n",
    "            elif mid < n:\n",
    "                return quicksort_search(mid+1, high)\n",
    "            else:\n",
    "                return quicksort_search(low, mid-1)\n",
    "            \n",
    "        res = quicksort_search(0, len(nums)-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "quick selection\n",
    "T: O(N)\n",
    "S: O(logN)\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        self.quickSelect(nums, n-k, 0, n-1)\n",
    "        return nums[n-k]\n",
    "\n",
    "\n",
    "    def quickSelect(self, nums: List[int], k: int, l: int, r: int) -> None:\n",
    "        \"\"\"make the kth smallest number of nums array in the right position\n",
    "           i.e., nums[:k] <= nums[k] <= nums[k+1:]\n",
    "           but nums array is not sorted\n",
    "        \"\"\"\n",
    "        if l > r:\n",
    "            return \n",
    "\n",
    "        idx = self.partition(nums, l, r)\n",
    "        if idx == k:\n",
    "            return \n",
    "        elif idx < k:\n",
    "            l = idx + 1 \n",
    "            # skip the left adjacent numbers with same value as nums[idx]\n",
    "            while l < k and nums[l] == nums[l - 1]:\n",
    "                l += 1\n",
    "            self.quickSelect(nums, k, l, r)\n",
    "        else:\n",
    "            r = idx-1\n",
    "            # skip the right adjacent numbers with same value as nums[idx]\n",
    "            while r > k and nums[r] == nums[r + 1]:\n",
    "                r -= 1\n",
    "            self.quickSelect(nums, k, l, r)\n",
    "\n",
    "    def partition(self, nums: list[int], l: int, r: int) -> int:\n",
    "        \"\"\"adapted from quick sort\n",
    "        in-place partitioning subarray nums[l, r] to 2 regions: nums[l, j-1] <= nums[j] <= nums[j+1, r]\n",
    "        return index j\n",
    "        \"\"\"\n",
    "        pivot = nums[l]    # choose the first item to be pivot\n",
    "        i, j = l+1, r\n",
    "\n",
    "        while i <= j:\n",
    "            # scan from left\n",
    "            while i < r and nums[i] <= pivot:\n",
    "                i += 1\n",
    "            # scan from right\n",
    "            while j > l and nums[j] > pivot:\n",
    "                j -= 1\n",
    "\n",
    "            # stop loop if pointers cross\n",
    "            if i >= j:\n",
    "                break \n",
    "            # swap 2 pointers\n",
    "            nums[i], nums[j] = nums[j], nums[i]\n",
    "        \n",
    "        # put pivot in the middle of 2 regions\n",
    "        nums[l], nums[j] = nums[j], nums[l]\n",
    "\n",
    "        return j\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def QSPivot(nums, start, end):\n",
    "            j = start + 1\n",
    "            pivot = start\n",
    "            for i in range(start + 1, end + 1):\n",
    "                if nums[i] <= nums[pivot]:\n",
    "                    nums[i], nums[j] = nums[j], nums[i]\n",
    "                    j += 1\n",
    "            nums[pivot], nums[j - 1] = nums[j - 1], nums[pivot]\n",
    "            pivot = j - 1\n",
    "            return pivot\n",
    "        def QucikSort(nums, start, end):\n",
    "            if start >= end:\n",
    "                return\n",
    "            pivot = QSPivot(nums, start, end)\n",
    "            QucikSort(nums, start, pivot - 1)\n",
    "            QucikSort(nums, pivot + 1, end)\n",
    "\n",
    "\n",
    "        QucikSort(nums, 0, len(nums) - 1)\n",
    "        return nums[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        def quick_select(left, right, k):\n",
    "            if left == right:\n",
    "                return nums[k]\n",
    "            pivot = nums[left]\n",
    "            i, j = left - 1, right + 1\n",
    "            while i < j:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "                while nums[i] < pivot:\n",
    "                    i += 1\n",
    "                while nums[j] > pivot:\n",
    "                    j -= 1\n",
    "                if i < j:\n",
    "                    nums[i], nums[j] = nums[j], nums[i]\n",
    "            if k <= j:\n",
    "                return quick_select(left, j, k)\n",
    "            return quick_select(j + 1, right, k)\n",
    "        return quick_select(0, len(nums) - 1, len(nums) - k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def quick_select(left, right, k):\n",
    "            if left == right:\n",
    "                return nums[k]\n",
    "            partition, i, j = nums[left], left - 1, right + 1\n",
    "            while i < j:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "                while nums[i] < partition:\n",
    "                    i += 1\n",
    "                while nums[j] > partition:\n",
    "                    j -= 1\n",
    "                if i < j:\n",
    "                    nums[i], nums[j] = nums[j], nums[i]\n",
    "            if k <= j:\n",
    "                return quick_select(left, j, k)\n",
    "            return quick_select(j + 1, right, k)\n",
    "        return quick_select(0, len(nums) - 1, len(nums) - k)\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
